{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Index Pairs of a String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #array #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #数组 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: indexPairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字符串的索引对"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给出&nbsp;<strong>字符串 </strong><code>text</code> 和&nbsp;<strong>字符串列表</strong> <code>words</code>, 返回所有的索引对 <code>[i, j]</code> 使得在索引对范围内的子字符串 <code>text[i]...text[j]</code>（包括&nbsp;<code>i</code>&nbsp;和&nbsp;<code>j</code>）属于字符串列表 <code>words</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre><strong>输入: </strong>text = &quot;thestoryofleetcodeandme&quot;, words = [&quot;story&quot;,&quot;fleet&quot;,&quot;leetcode&quot;]\n",
    "<strong>输出: </strong>[[3,7],[9,13],[10,17]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre><strong>输入: </strong>text = &quot;ababa&quot;, words = [&quot;aba&quot;,&quot;ab&quot;]\n",
    "<strong>输出: </strong>[[0,1],[0,2],[2,3],[2,4]]\n",
    "<strong>解释: \n",
    "</strong>注意，返回的配对可以有交叉，比如，&quot;aba&quot; 既在 [0,2] 中也在 [2,4] 中\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>所有字符串都只包含小写字母。</li>\n",
    "\t<li>保证 <code>words</code> 中的字符串无重复。</li>\n",
    "\t<li><code>1 &lt;= text.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 20</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 50</code></li>\n",
    "\t<li>按序返回索引对 <code>[i,j]</code>（即，按照索引对的第一个索引进行排序，当第一个索引对相同时按照第二个索引对排序）。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [index-pairs-of-a-string](https://leetcode.cn/problems/index-pairs-of-a-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [index-pairs-of-a-string](https://leetcode.cn/problems/index-pairs-of-a-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"thestoryofleetcodeandme\"\\n[\"story\",\"fleet\",\"leetcode\"]', '\"ababa\"\\n[\"aba\",\"ab\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:\n",
    "        words = set(words)\n",
    "        ans = []\n",
    "        text = list(text)\n",
    "        for l in range(len(text)):\n",
    "            for r in range(l,len(text)):\n",
    "                if ''.join(text[l:r + 1]) in words:\n",
    "                    ans.append([l,r])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:\n",
    "        res = []\n",
    "\n",
    "        for i in words:\n",
    "            for j in range(len(text)):\n",
    "\n",
    "                if text[j: j + len(i)] == i:\n",
    "                    res.append([j, j + len(i) - 1])\n",
    "            \n",
    "        return sorted(res, key = lambda x:  (x[0], x[1]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:\n",
    "        res = []\n",
    "\n",
    "        for i in words:\n",
    "            for j in range(len(text)):\n",
    "\n",
    "                if text[j: j + len(i)] == i:\n",
    "                    res.append([j, j + len(i) - 1])\n",
    "            \n",
    "        return sorted(res, key = lambda x:  (x[0], x[1]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        for x in words:\n",
    "            s = text\n",
    "            while (i := s.find(x)) != -1:\n",
    "                ans.append([i,i+len(x)-1])\n",
    "                s = '-' * (i+1) + s[i+1:]\n",
    "        ans.sort()\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:\n",
    "        wordDict = collections.defaultdict(set)\n",
    "        for word in words:\n",
    "            wordDict[len(word)].add(word)\n",
    "        \n",
    "        wordLen = sorted(wordDict.keys())\n",
    "        n = len(text)\n",
    "        ans = []\n",
    "        for i in range(n - wordLen[0] + 1):\n",
    "            for j in wordLen:\n",
    "                if i + j > n:   break\n",
    "                if text[i:i+j] in wordDict[j]:\n",
    "                    ans.append([i, j+i-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:\n",
    "        a = []\n",
    "        for w in words:\n",
    "            t = text.find(w)\n",
    "            while t >= 0:\n",
    "                a.append([t, t + len(w) - 1])\n",
    "                t = text.find(w, t + 1)\n",
    "        return sorted(a, key=lambda x: [x[0], x[1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:\n",
    "        words.sort(key=lambda x: len(x))\n",
    "        print(words)\n",
    "        ans = []\n",
    "        n = len(text)\n",
    "        for i in range(n):\n",
    "            for word in words:\n",
    "                m = len(word)\n",
    "                # for i in range(0,len(text)-n):\n",
    "                if text[i:i + m] == word:\n",
    "                    ans.append([i, i + m - 1])\n",
    "        # print(ans)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        for x in words:\n",
    "            s = text\n",
    "            while (i := s.find(x)) != -1:\n",
    "                ans.append([i,i+len(x)-1])\n",
    "                s = 'A' * (i+1) + s[i+1:]\n",
    "        ans.sort()\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def min_(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:\n",
    "        \n",
    "        dct = set(words)\n",
    "        ans = []\n",
    "        n = len(text)\n",
    "        for i in range(n):\n",
    "            for j in range(i, min_(i+51, n)):\n",
    "                if text[i:j+1] in dct:\n",
    "                    ans.append([i, j])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:\n",
    "        l = [len(i) for i in words]\n",
    "        new_list = []\n",
    "        for i in range(len(text)):\n",
    "            for j, v in enumerate(l):\n",
    "                if text[i: i+v] == words[j]:\n",
    "                    new_list.append([i, i+v-1])\n",
    "        new_list.sort()\n",
    "        return new_list\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:\n",
    "        n=len(text)\n",
    "        w=len(words)\n",
    "        res=[]\n",
    "        for i in range(w):\n",
    "            wlen=len(words[i])\n",
    "            for j in range(n-wlen+1):\n",
    "                if text[j:j+wlen]==words[i]:\n",
    "                    res.append([j,j+wlen-1])\n",
    "        res.sort(key= lambda x:(x[0],x[1]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:\n",
    "        res = []\n",
    "\n",
    "        for i in words:\n",
    "            for j in range(len(text)):\n",
    "\n",
    "                if text[j: j + len(i)] == i:\n",
    "                    res.append([j, j + len(i) - 1])\n",
    "            \n",
    "        return sorted(res, key = lambda x:  (x[0], x[1]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:\n",
    "        n=len(text)\n",
    "        ans=[]\n",
    "        for word in words:\n",
    "            m=len(word)\n",
    "            for i in range(n):\n",
    "                if text[i:i+m]==word:\n",
    "                    ans.append([i,i+m-1])\n",
    "                    # break\n",
    "        return sorted(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:\n",
    "        return sorted([[m.start(), m.start()+len(w)-1] for w in words for m in re.finditer('(?={0})'.format(w), text)])\n",
    "        \n",
    "    # 自定义排序规则\n",
    "    def indexPairs2(self, text: str, words: List[str]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for one in words:\n",
    "            for i in range(len(text)):\n",
    "                if text[i] == one[0]:\n",
    "                    if text[i: i+len(one)] == one:\n",
    "                        res.append([i, i+len(one)-1])\n",
    "        def cmp(a, b):  # 自定义排序方式\n",
    "            if a[0] == b[0]:\n",
    "                if a[1] >= b[1]: return 1\n",
    "                else: return -1\n",
    "            else:\n",
    "                if a[0] >= b[0]: return 1\n",
    "                else: return -1\n",
    "        import functools\n",
    "        res = sorted(res, key= functools.cmp_to_key(cmp))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:\n",
    "        res = list()\n",
    "        tlen = len(text)\n",
    "        for w in words:\n",
    "            wlen = len(w)\n",
    "            for i in range(tlen-wlen+1):\n",
    "                if text[i:i+wlen] == w:\n",
    "                    res.append([i,i+wlen-1])\n",
    "        res.sort(key=lambda x:(x[0],x[1]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:\n",
    "        res = []\n",
    "\n",
    "        for i in words:\n",
    "            for j in range(len(text)):\n",
    "\n",
    "                if text[j: j + len(i)] == i:\n",
    "                    print(text[j: j + len(i) - 1])\n",
    "                    res.append([j, j + len(i) - 1])\n",
    "            \n",
    "        return sorted(res, key = lambda x:  (x[0], x[1]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\r\n",
    "    def __init__(self):\r\n",
    "        self.child = dict()\r\n",
    "        self.isWord = False\r\n",
    "    \r\n",
    "    def insert(self, word: str):\r\n",
    "        root = self\r\n",
    "        for c in word:\r\n",
    "            if c not in root.child:\r\n",
    "                root.child[c] = Trie()\r\n",
    "            root = root.child[c]\r\n",
    "        root.isWord = True\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:\r\n",
    "        n = len(text)\r\n",
    "\r\n",
    "        T = Trie()\r\n",
    "        for word in words:\r\n",
    "            T.insert(word)\r\n",
    "        \r\n",
    "        res = []\r\n",
    "        for i, c in enumerate(text):\r\n",
    "            root = T\r\n",
    "            if c not in root.child:\r\n",
    "                continue\r\n",
    "            j = i\r\n",
    "            while j < n and text[j] in root.child:\r\n",
    "                root = root.child[text[j]]\r\n",
    "                if root.isWord == True:\r\n",
    "                    res.append([i, j])\r\n",
    "                j += 1\r\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
